package 力扣日常刷题.木22二月.第08天214;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 帅小伙
 * @date 2022/2/14
 * @description
 */
public class Demo58JZ机器人的运动范围 {


    public int movingCount(int m, int n, int k) {
        if (k == 0) return 1;
        Queue<int[]> queue = new LinkedList<>();
        int[] dx = {0, 1};
        int[] dy = {1, 0};
        queue.offer(new int[]{0, 0});
        boolean[][] isVis = new boolean[m][n];
        int ans = 1;
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int x = poll[0], y = poll[1];

            for (int i = 0; i < 2; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= m || ny >= n || isVis[nx][ny] || get(nx) + get(ny) > k) continue;
                queue.offer(new int[]{nx, ny});
                isVis[nx][ny] = true;
                ans++;
            }
        }
        return ans;
    }

    public int get(int x) {
        int ans = 0;
        while (x != 0) {
            ans += x % 10;
            x /= 10;
        }
        return ans;
    }

}
